class Solution
{
public:
    vector<int> resultArray(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> arr1{nums[0]};
        vector<int> arr2{nums[1]};
        vector<int> sortedArr1{nums[0]};
        vector<int> sortedArr2{nums[1]};

        for (int i = 2; i < n; i++)
        {
            auto p1 = upper_bound(sortedArr1.begin(), sortedArr1.end(), nums[i]);
            auto p2 = upper_bound(sortedArr2.begin(), sortedArr2.end(), nums[i]);
            int c1 = sortedArr1.end() - p1;
            int c2 = sortedArr2.end() - p2;
            if (c1 > c2)
            {
                arr1.push_back(nums[i]);
                sortedArr1.insert(p1, nums[i]);
            }
            else if (c1 < c2)
            {
                arr2.push_back(nums[i]);
                sortedArr2.insert(p2, nums[i]);
            }
            else
            {
                if (arr1.size() <= arr2.size())
                {
                    arr1.push_back(nums[i]);
                    sortedArr1.insert(p1, nums[i]);
                }
                else
                {
                    arr2.push_back(nums[i]);
                    sortedArr2.insert(p2, nums[i]);
                }
            }
        }
        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
        return arr1;
    }
};